Rational Root Lemma

Theorem

Suppose

\[ f(z) = a_n z^n + a_{n - 1} z^{n - 1} + \dots + a_1 z + a_0\]

is a polynomial with integer coefficients \(a_i\). If \(f\) has a rational root \(\frac{p}{q}\) written in lowest form then

\[ p \mid a_0 \quad \text{and} \quad q \mid a_n.\]

Using the divisor counting function, this narrows down the number of possible rational roots to check to at most \(2 d(a_0) d(a_n)\) where the \(2\) comes from both positive and negative cases. Because of this, any common factor of the coefficients should be removed to reduce the number of possible cases to check.

Similarly, any rational polynomial can have it's denominators cleared such that the above theorem applies.

Proof

Suppose \(\frac{p}{q}\) is a rational root of \(f\) with \(\gcd(p, q) = 1\). This means that

\[ f\left(\frac{p}{q}\right) = a_n \left(\frac{p}{q}\right)^n + a_{n - 1} \left(\frac{p}{q}\right)^{n - 1} + \dots + a_1 \left(\frac{p}{q}\right) + a_0 = 0.\]

Multiplying through by \(q^{n}\) leads to an equation

\[ a_n p^n + a_{n - 1} p^{n - 1} q + \dots + a_1 p q^{n - 1} + a_0 q^n = 0. \tag{1}\]

As such, moving \(a_n p^n\) to the other side and factoring out \(q\) we have that

\[ q\left(a_{n - 1} p^{n - 1} + \dots + a_1 p q^{n - 2} + a_0 q^{n - 1}\right) = -a_n p^n.\]

Given that both sides of this equation are integers, we can conclude that \(q \mid -a_n p^n\) and hence that \(q \mid a_n\) by Euclid's lemma and the fact that \(\gcd(p, q) = 1\).

We can also, from (1), move \(a_0 q^n\) to the other side and factor out the \(q\) to conclude similarly that \(p \mid a_0\).